package com.mzy.linear_struct;


import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;

/**
 * @Author: codermzy
 * @Date: 2024/04/09/12:50
 * @Description:
 */
public class BSTree {
    private TreeNode root;

    static class TreeNode {
        Integer value;
        TreeNode left;
        TreeNode right;

        public TreeNode(Integer value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }


    public void insert(Integer value) {

        TreeNode newNode = new TreeNode(value);

        // 判断是否是第一次插入
        if (root == null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }


    }

    public void preOrderTraverse(Consumer<Integer> consumer) {
        preOrderTraverseNode(root, consumer);
    }

    private void preOrderTraverseNode(TreeNode root, Consumer<Integer> consumer) {
        if (root == null) {
            return;
        }
        consumer.accept(root.value);
        preOrderTraverseNode(root.left, consumer);
        preOrderTraverseNode(root.right, consumer);
    }

    public void inOrderTraverse() {
        inOrderTraverseNode(root);
    }

    private void inOrderTraverseNode(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraverseNode(root.left);
        System.out.println(root);
        inOrderTraverseNode(root.right);
    }


    public void postOrderTraverse() {
        postOrderTraverseNode(root);
    }

    private void postOrderTraverseNode(TreeNode root) {
        if (root == null) {
            return;
        }

        postOrderTraverseNode(root.left);
        postOrderTraverseNode(root.right);
        System.out.println(root);
    }


    private void insertNode(TreeNode root, TreeNode newNode) {


        if (root.value > newNode.value) {

            if (root.left == null) {

                root.left = newNode;
            } else {
                insertNode(root.left, newNode);
            }
        } else if (root.value < newNode.value) {
            if (root.right == null) {
                root.right = newNode;
            } else {
                insertNode(root.right, newNode);
            }
        }


    }


    public void levelOrderTraverse() {

        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

    }


    public int getMax() {
        TreeNode current = root;
        int max = 0;
        while (current != null && current.right != null) {
            TreeNode rightNode = current.right;
            max = rightNode.value;
            current = current.right;
        }
        return max;
    }

    public int getMin() {
        TreeNode current = root;
        int min = 0;
        while (current != null && current.left != null) {
            TreeNode leftNode = current.left;
            min = leftNode.value;
            current = current.left;
        }
        return min;
    }


    public boolean search(Integer value) {
        TreeNode current = root;
        while (current != null) {
            if (value.equals(current.value)) return true;

            if (value > current.value) current = current.right;
            if (value < current.value) current = current.left;
        }
        return false;
    }
    private boolean remove(Integer value) {
        TreeNode current = root;
        TreeNode parent = null;
        // left 为false ， right 为true
        boolean flag = false;
        boolean isExist = false;
        while (current != null) {
            if(value.equals(current.value)) {
                isExist = true;
                break;
            }
            parent = current;
            if (current.value > value) {
                current = current.left;
                flag = false;
            } else {
                current = current.right;
                flag = true;
            }
        }
        if (flag) {
            parent.right = null;
        } else {
            parent.left = null;
        }


        return isExist;
    }
    public static void main(String[] args) {
        BSTree tree = new BSTree();
        tree.insert(11);
        tree.insert(7);
        tree.insert(15);
        tree.insert(5);
        tree.insert(9);
        tree.insert(3);
        tree.insert(6);
        tree.insert(8);
        tree.insert(10);
        tree.insert(13);
        tree.insert(20);
        tree.insert(12);
        tree.insert(14);
        tree.insert(18);
        tree.insert(25);
        // tree.preOrderTraverse(System.out::println);
        // System.out.println(tree.getMax());
        // System.out.println(tree.getMin());
        tree.levelOrderTraverse();
        tree.remove(3);
        //
        // System.out.println(tree.search(6));
        // System.out.println(tree.search(41));
        // System.out.println(tree.search(0));
    }


}
